package org.example.algorithm.linkedlist;

public class SwapPairsSolution {

    //1-3-5-7-9 => 3-1-7-5-9
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null && cur.next != null) {
            if (pre != null) {
                pre.next = cur.next;
            }
            ListNode unDealNode = cur.next.next;
            cur.next.next = cur;
            cur.next = unDealNode;
            pre = cur;
            cur = cur.next;
        }
        return newHead;
    }

    public ListNode swapPairs(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode newNode = node.next;
        node.next = swapPairs(node.next.next);
        newNode.next = node;
        return newNode;
    }

    //定义哑节点
    //1-2-3-4 => 2-1-4-3
    public ListNode swapPairs3(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode dummy = new ListNode(0, node);
        ListNode node0 = dummy;
        ListNode node1 = node;
        while (node1 != null && node1.next != null) {
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;

            node0.next = node2;
            node2.next = node1;
            node1.next = node3;

            node0 = node1;
            node1 = node3;
        }
        return dummy.next;
    }
}
